#include<iostream>
#include<stack>
#include<vector>
using namespace std;
struct Node
{
    string data;
	Node* left;
	Node* right;
};
//查找二叉树指定节点
 
Node* target = NULL;
void creat(Node*& T, string kk)
{
    string ch;
    cin >> ch;
    if (ch == kk)
    {
        T = NULL;
    }//但凡输入了#号 该节点下一位停止
    else
    {
        T = new Node;
        T->data = ch;
        creat(T->left, kk);
        creat(T->right, kk);
    }
}
 
 
void find(Node* root, string x)//用来寻找结点的地址 
{
	Node* p = root;
	if (p == NULL)
	{
		return;
	}
	else if (p->data == x)
	{
 
		target = p;//核心 找到p的地址 抓包给全局变量 target现在的值就是所求的地址
	}
 
	else if (p != NULL && p->data != x)
	{
		find(p->left, x);
		find(p->right, x);
	}
}
 
 
 
 
bool display(Node* pRoot, Node* pNode, vector<string>& v)
{
	if (pRoot == NULL)
	{
		return false;
	}
	v.push_back(pRoot->data);
	bool found = false;
	if (pRoot == pNode)//还是比较指针稳妥，节点值有可能重复
	{
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << " ";
		cout << endl;
		return true;
	}
	if (!found && pRoot->left)
	{
		found = display(pRoot->left, pNode, v);
	}
 
	//一旦左子树中找到节点，就不需要再遍历右子树
	if (!found && pRoot->right)
	{
		found = display(pRoot->right, pNode, v);
	}
	if (!found)
		v.pop_back();
	return found;
}
 
 
 
int main()
{
	Node* root;
	string kk;
	cout << "请输入表示终止的符号:" << endl;
	cin >> kk;
	cout << "现在请输入你的二叉树 请用先序遍历输入" << endl;
	creat(root, kk);
	vector<string>m;
	cout << "输入你要找的节点" << endl;
	string x;
	cin >> x;	
	find(root, x);
	cout << "路径如下：" << endl;
	display(root, target, m);
	return 0;
}